With modem computer systems, it is now a common practice to present images, such as pages of text, with a computer system. For example, the pages can be pages of books, or "pages" of information obtained via a communication network such as the Internet. Users of the computer systems may desire to view a large number of images. These images can consume large amounts of memory storage. It is desired to reduce the storage required for digital images. Compressed images can be processed and communicated in less time.
Typically, the images are stored as pixel elements, each pixel element indicates the level of illumination, or blackness on paper that should be used during the rendering of the element on a display screen. If four levels of grey-scale are used, then each pixel consumes 2 bits.
Since the data typically need to be compressed only once prior to subsequent repeated use, the time required to compress the pixel data is of minor concern. However, decompressing an encoded page of text should take no longer than turning a real page.
In addition, it is desired to compress images which are to be displayed using anti-aliasing techniques. For example, frequently a scanned image includes 300 dots per inch (dpi). However, many display systems can only display pixels at resolutions of 100 dpi. Displaying lines which are slanted with respect to the orientation of the pixels usually results in a jagged or step-like appearance. Anti-aliasing uses an intermediate level of the grey-scale to "smooth" the jagged appearance of the lines.
Prior art techniques for compressing images, such as JPEG for moving pictures, are generally too slow and coarse for recovering and rendering quality text images in a relatively short time. For example, decompression should take no more than a couple of seconds per page. Compression schemes developed for digitized facsimiles are more appropriate. Typical facsimile (FAX) compression schemes can reach an eight to one 8:1 compression ratio.
In the prior art, two types of compression techniques are known for bi-level or two-tone (black and white) images of text The techniques are either pixel based or mark (character) based. Pixel based techniques include JBIG, FELICS, and MGBILEVEL. These schemes consider and encode each pixel individually. For example, the shade of each pixel is encoded according to the shades of the surrounding pixels.
Mark based schemes attempt to derive or infer the original marks or characters from the image of the text. Schemes based on marks, such as MGTIC, typically store information regarding mark boundaries identified with derived or provided font information. In other words, with character based compression, the text is partitioned according to a shape of the underlying characters which form the text. Mark based systems tend to be relatively inefficient All of these bi-level techniques are described in "Managing Giagabyte: Compressing indexed documents and text," Moffat and Bell, Van Nostrand Reinhold, 1994.
It is desired to provide a compression scheme for grey-scale text images which yields a compression ratio at least as good, if not better than what is known in the prior art. Furthermore, it is desired that the time required to decompress the encode data be reduced during rendering of the images.